home *** CD-ROM | disk | FTP | other *** search
/ Box' of X 3 / Box' of X 3.iso / x-viewer / amiga / anim / skip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-05-06  |  11.4 KB  |  475 lines
  1.  
  2. /***************************************************************************
  3. *
  4. *  This contains routines to compress images one of two ways:
  5. *      1. Vertical Byte Run Length (VRUN)
  6. *      2. Vertical Byte Run Length With Skips (SKIP)
  7. *   from amiga/programs #274, dated jul 8 1987...
  8. *
  9. * The routines here compress a single bit-plane.  There's routines to
  10. * see how big the compressed result will be (xxxx_count_plane() )
  11. * and routines to actually compress the result into a buffer in memory
  12. * (xxxx_comp_plane() )  where xxxx is either vrun or skip depending....
  13. *
  14. *
  15. * VRUN compression format:
  16. *    a VRUN-compressed plane is a concatenation of VRUN-compressed columns.
  17. *    Each column is an op-count followed by a concatenation of op-count op's.
  18. *    An op is in one of these two formats:
  19. *        SAME_OP:  1-byte-count  followed by 1-byte to repeat count times.
  20. *        UNIQ_OP:  1-byte-count  followed by count bytes of data to copy 
  21. *    The counts in either op must be 127 or less.  If it's a UNIQ_OP the
  22. *    hi bit of the count op is set (it's masked with 127 to find the actual
  23. *    count).
  24. *
  25. * SKIP compression format:
  26. *    a SKIP compressed plane is a concatenation of SKIP-compressed columns.
  27. *    Like a VRUN this is an op-count followed by a concatenation of op;s.
  28. *    However in this one we have 3 op formats:
  29. *       SKIP_OP:  Hi bit clear.  Count of bytes to skip.
  30. *       UNIQ_OP:  Hi bit set.  Remainder is count of data to copy. Data 
  31. *                 follows immediately.
  32. *       SAME_OP:  A zero followed by a one-byte-count followed by one byte
  33. *                 of data to repeat count times.
  34. *
  35. ***************************************************************************/
  36.  
  37. #include <exec/types.h>
  38. #include <graphics/gfx.h>
  39.  
  40. #define MAXRUN 127
  41.  
  42. static WORD linebytes = 40;
  43. static WORD uniq_count;
  44. static unsigned char *uniq;
  45. static WORD op_count;
  46.  
  47.  
  48. /* count up how many in a column are the same between in and last_in ...
  49.    ie how big of a "skip" can we go on. */
  50. vskip(in, last_in,  count)
  51. register unsigned char *in;
  52. register unsigned char *last_in;
  53. register WORD count;
  54. {
  55. register WORD skips;
  56.  
  57. skips = 0;
  58. while (--count >= 0) {
  59.     if (*in != *last_in)
  60.         break;
  61.     in += linebytes;
  62.     last_in += linebytes;
  63.     skips++;
  64. }
  65. return(skips);
  66. }
  67.  
  68. /* vsame() - count up how many in a row (vertically) are the same as the
  69.    first one ... ie how big of a "same" op we can have */
  70. vsame(in,  count)
  71. register unsigned char *in;
  72. register WORD count;
  73. {
  74. register unsigned char c;
  75. register WORD same;
  76.  
  77. c = *in;
  78. in += linebytes;
  79. --count;
  80. same = 1;
  81. while (--count >= 0)
  82.     {
  83.     if (*in != c)
  84.         break;
  85.     same++;
  86.     in += linebytes;
  87.     }
  88. return(same);
  89. }
  90.  
  91.  
  92. /* skip_count_line() - figure out what size this column will compress
  93.    to using vertical-byte-run-length-with-skips encoding */
  94. skip_count_line(in, last_in, count)
  95. register unsigned char *in;
  96. register unsigned char *last_in;
  97. WORD  count;
  98. {
  99. WORD local_count;
  100. WORD a_run;
  101. WORD run_length;
  102. WORD uniq_count = 0;
  103. WORD comp_count = 1; /* one for the op count */
  104.  
  105.  
  106. if (vskip(in, last_in, count) == count)  /* skip whole column? */
  107.     return(1);
  108. for (;;) {
  109.     if (count <= 0)
  110.         break;
  111.     local_count = (count < MAXRUN ? count : MAXRUN);
  112.     a_run = 0;
  113.     if ((run_length = vskip(in, last_in, local_count)) > 1) {
  114.         count -= run_length;
  115.         if (count > 0)    /* the last skip disappears */
  116.             comp_count += 1;
  117.         a_run = 1;
  118.     }
  119.     else if ((run_length = vsame(in, local_count)) > 3) {
  120.         count -= run_length;
  121.         a_run = 1;
  122.         comp_count += 3;
  123.     }
  124.     if (a_run) {
  125.         in += run_length*linebytes;
  126.         last_in += run_length*linebytes;
  127.         if (uniq_count > 0) {
  128.             comp_count += uniq_count+1;
  129.             uniq_count = 0;
  130.         }
  131.     } else {
  132.         in += linebytes;
  133.         last_in += linebytes;
  134.         uniq_count++;
  135.         count -= 1;
  136.         if (uniq_count == MAXRUN) {
  137.             comp_count += uniq_count+1;
  138.             uniq_count = 0;
  139.         }
  140.     }
  141. }
  142. if (count != 0) {
  143.     printf("weird end count %d in skip_line_count\n");
  144. }
  145. if (uniq_count != 0) {
  146.     comp_count += uniq_count+1;
  147. }
  148. return(comp_count);
  149. }
  150.  
  151. /* skip_count_plane() - figure out what size this plane will compress
  152.    to using vertical-byte-run-length-with-skips encoding */
  153. skip_count_plane(in, last_in, next_line, rows)
  154. unsigned char *in;
  155. unsigned char *last_in;
  156. WORD  next_line;
  157. WORD  rows;
  158. {
  159. WORD i;
  160. WORD comp_count;
  161.  
  162. linebytes = next_line;
  163. comp_count = 0;
  164. i = next_line;
  165. while (--i >= 0)
  166.     {
  167.     comp_count += skip_count_line(in, last_in, rows);
  168.     in++;
  169.     last_in++;
  170.     }
  171. return(comp_count);
  172. }
  173.  
  174. /* flush_uniq() - write out the "uniq" run that's been accumulating while
  175.    we've been looking for skips and "same" runs. */
  176. unsigned char *
  177. flush_uniq(stuff)
  178. unsigned char *stuff;
  179. {
  180. if (uniq_count > 0)
  181.     {
  182.     op_count++;
  183.     *stuff++ = (uniq_count | 0x80);
  184.     copy_line_to_chars(uniq, stuff, linebytes, uniq_count);
  185.     stuff += uniq_count;
  186.     uniq_count = 0;
  187.     }
  188. return(stuff);
  189. }
  190.  
  191. copy_line_to_chars(in,out,linebytes,count)
  192. unsigned char *in,*out;
  193. int linebytes,count;
  194. {
  195.    while (count--) {
  196.       *out = *in;
  197.       out++;
  198.       in += linebytes;
  199.    }
  200.    return(0);
  201. }
  202.  
  203. /* skip_comp_line() - Compress "in" into "out" using vertical-byte-run-
  204.    with-skips encodeing. Return pointer to "out"'s next free space. */
  205. unsigned char *
  206. skip_comp_line(in, last_in, out, count)
  207. register unsigned char *in;
  208. unsigned char *last_in;
  209. unsigned char *out;
  210. WORD  count;
  211. {
  212. register unsigned char *stuffit;
  213. WORD local_count;
  214. WORD a_run;
  215. WORD run_length;
  216.  
  217. /* if can skip over whole column, then compact a bit by just setting the
  218.    "op count" for this column to zero */
  219. if (vskip(in, last_in, count) == count)  /* skip whole column? */ {
  220.     *out++ = 0;
  221.     return(out);
  222. }
  223.  
  224. op_count = 0;    /* haven't done any op's yet */
  225.  
  226. /* initialize variables which keep track of how many uniq bytes we've gone
  227.    past, and where uniq run started. */
  228. uniq_count = 0; 
  229. uniq = in;
  230.  
  231. stuffit = out+1; /* skip past "op-count" slot in out array */
  232. for (;;) {
  233.     if (count <= 0)
  234.         break;
  235.     local_count = (count < MAXRUN ? count : MAXRUN);
  236.     a_run = 0;  /* first assume not a skip or a same run */
  237.     /* see how much could skip from here.  Two or more is worth skipping! */
  238.     if ((run_length = vskip(in, last_in, local_count)) > 1) {
  239.         a_run = 1;
  240.         count -= run_length;
  241.         stuffit = flush_uniq(stuffit); /* flush pending "uniq" run */
  242.         if (count > 0)    /* last skip vanishes */ {
  243.             op_count++;
  244.             *stuffit++ = run_length;
  245.         }
  246.     }
  247.     /* four or more of the same byte in a row compresses too */
  248.     else if ((run_length = vsame(in, local_count)) > 3) {
  249.         a_run = 1;
  250.         count -= run_length;
  251.         op_count++;
  252.         stuffit = flush_uniq(stuffit); /* flush pending "uniq" run */
  253.         *stuffit++ = 0;
  254.         *stuffit++ = run_length;
  255.         *stuffit++ = *in;
  256.     }
  257.     /* if it's a run of some sort update in and last_in pointer, and
  258.        reset the uniq pointer to the current position */
  259.     if (a_run) {
  260.         in += run_length*linebytes;
  261.         last_in += run_length*linebytes;
  262.         uniq = in;
  263.     /* otherwise just continue accumulating stuff in uniq for later flushing
  264.        or immediate if it get's past MAXRUN */
  265.     } else {
  266.         in += linebytes;
  267.         last_in += linebytes;
  268.         uniq_count++;
  269.         count -= 1;
  270.         if (uniq_count == MAXRUN) {
  271.             stuffit = flush_uniq(stuffit);
  272.             uniq = in;
  273.         }
  274.     }
  275. }
  276. /* if came to end of column within a uniq-run still have to flush it */
  277. if (uniq_count != 0) {
  278.     stuffit = flush_uniq(stuffit);
  279. }
  280. if (count != 0) {
  281.     printf("weird end count %d in skip_line_count\n", count);
  282. }
  283. /* and stuff the first byte of this (compressed) column with the op_count */
  284. *out = op_count;
  285. return(stuffit);
  286. }
  287.  
  288. /* skip_comp_plane() - Compress "in" into "out" using vertical-byte-run-
  289.    with-skips encodeing. Return pointer to "out"'s next free space. */
  290. unsigned char *
  291. skip_comp_plane(in, last_in, out, next_line, rows)
  292. unsigned char *in;
  293. unsigned char *last_in;
  294. unsigned char *out;
  295. WORD  next_line;
  296. WORD  rows;
  297. {
  298. WORD i;
  299. unsigned char *last_out = out;
  300.  
  301. linebytes = next_line;
  302. i = next_line;
  303. while (--i >= 0) {
  304.     out = skip_comp_line(in, last_in, out, rows);
  305.     last_out = out;
  306.     in++;
  307.     last_in++;
  308. }
  309. return(out);
  310. }
  311.  
  312. /* vrun_count_line() - figure out what size this column will compress
  313.    to using vertical-byte-run-length encoding */
  314. vrun_count_line(in, count)
  315. register unsigned char *in;
  316. WORD  count;
  317. {
  318. WORD local_count;
  319. WORD a_run;
  320. WORD run_length;
  321. WORD uniq_count = 0;
  322. WORD comp_count = 1; /* one for the op count */
  323.  
  324.  
  325. for (;;)
  326.     {
  327.     if (count <= 0)
  328.         break;
  329.     local_count = (count < MAXRUN ? count : MAXRUN);
  330.     a_run = 0;
  331.     if ((run_length = vsame(in, local_count)) > 2)
  332.         {
  333.         a_run = 1;
  334.         comp_count += 2;
  335.         }
  336.     if (a_run)
  337.         {
  338.         in += run_length*linebytes;
  339.         count -= run_length;
  340.         if (uniq_count > 0)
  341.             {
  342.             comp_count += uniq_count+1;
  343.             uniq_count = 0;
  344.             }
  345.         }
  346.     else
  347.         {
  348.         in += linebytes;
  349.         uniq_count++;
  350.         count -= 1;
  351.         if (uniq_count == MAXRUN)
  352.             {
  353.             comp_count += uniq_count+1;
  354.             uniq_count = 0;
  355.             }
  356.         }
  357.     }
  358. if (count != 0)
  359.     {
  360.     printf("weird end count %d in vrun_line_count\n");
  361.     }
  362. if (uniq_count != 0)
  363.     {
  364.     comp_count += uniq_count+1;
  365.     }
  366. return(comp_count);
  367. }
  368.  
  369. /* vrun_count_plane() - figure out what size this plane will compress
  370.    to using vertical-byte-run-length encoding */
  371. vrun_count_plane(in, next_line, rows)
  372. unsigned char *in;
  373. WORD  next_line;
  374. WORD  rows;
  375. {
  376. WORD i;
  377. WORD comp_count;
  378.  
  379. linebytes = next_line;
  380. comp_count = 0;
  381. i = next_line;
  382. while (--i >= 0)
  383.     {
  384.     comp_count += vrun_count_line(in, rows);
  385.     in++;
  386.     }
  387. return(comp_count);
  388. }
  389.  
  390.  
  391. /* vrun_comp_line() - Compress "in" into "out" using vertical-byte-run
  392.    encodeing. Return pointer to "out"'s next free space. */
  393. unsigned char *
  394. vrun_comp_line(in, out, count)
  395. register unsigned char *in;
  396. unsigned char *out;
  397. WORD  count;
  398. {
  399. register unsigned char *stuffit;
  400. WORD local_count;
  401. WORD a_run;
  402. WORD run_length;
  403.  
  404. uniq_count = op_count = 0;
  405. uniq = in;
  406.  
  407. stuffit = out+1;
  408. for (;;)
  409.     {
  410.     if (count <= 0)
  411.         break;
  412.     local_count = (count < MAXRUN ? count : MAXRUN);
  413.     a_run = 0;
  414.     if ((run_length = vsame(in, local_count)) > 2)
  415.         {
  416.         a_run = 1;
  417.         stuffit = flush_uniq(stuffit);
  418.         *stuffit++ = run_length;
  419.         *stuffit++ = *in;
  420.         }
  421.     if (a_run)
  422.         {
  423.         op_count++;
  424.         in += run_length*linebytes;
  425.         count -= run_length;
  426.         uniq = in;
  427.         }
  428.     else
  429.         {
  430.         in += linebytes;
  431.         uniq_count++;
  432.         count -= 1;
  433.         if (uniq_count == MAXRUN)
  434.             {
  435.             stuffit = flush_uniq(stuffit);
  436.             uniq = in;
  437.             }
  438.         }
  439.     }
  440. if (uniq_count != 0)
  441.     {
  442.     stuffit = flush_uniq(stuffit);
  443.     }
  444. if (count != 0)
  445.     {
  446.     printf("weird end count %d in vrun_line_count\n", count);
  447.     }
  448. *out = op_count;
  449. return(stuffit);
  450. }
  451.  
  452. /* vrun_comp_plane() - Compress "in" into "out" using vertical-byte-run
  453.    encodeing. Return pointer to "out"'s next free space. */
  454. unsigned char *
  455. vrun_comp_plane(in, out, next_line, rows)
  456. unsigned char *in;
  457. unsigned char *out;
  458. WORD  next_line;
  459. WORD  rows;
  460. {
  461. WORD i;
  462. unsigned char *last_out = out;
  463.  
  464. linebytes = next_line;
  465. i = next_line;
  466. while (--i >= 0)
  467.     {
  468.     out = vrun_comp_line(in, out, rows);
  469.     last_out = out;
  470.     in++;
  471.     }
  472. return(out);
  473. }
  474.  
  475.